package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-08-29 15:46
 */


/**
 * 题目：给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。
 * <p>
 * 注意：
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1
 */


public class Test12_整数除法 {
    public int divide(int dividend, int divisor) {
        //Integer最大正整数小于最小数的绝对值，因此要保证结果不会溢出
        if (dividend == Integer.MIN_VALUE && divisor == -1) {
            return Integer.MAX_VALUE;
        }

        //将正数都转换为负数，应为负数的范围比正数大
        //记录负数的个数，并将两数都转为负数
        int negative = 2;
        if (dividend > 0) {
            negative--;
            dividend = -dividend;
        }
        if (divisor > 0) {
            negative--;
            divisor = -divisor;
        }
        //两个负数的除法
        int result = divideCore(dividend, divisor);
        //根据负号对商进行符号的修改
        return negative == 1 ? -result : result;
    }

    private int divideCore(int dividend, int divisor) {
        int result = 0;
        //注意是两个负数的比较大小
        while (dividend <= divisor) {
            //value用来存储除数翻倍后的值
            int value = divisor;
            //quotient用来存储除数翻的倍数
            int quotient = 1;
            //除数每次从1倍开始翻倍。直到-2^31的一半-2^30
            while (value >= (Integer.MIN_VALUE >> 1) && dividend <= (value << 1)) {
                quotient <<= 1;
                value <<= 1;
            }
            //倍数累加为商
            result += quotient;
            //被除数减去这部分除数翻倍后的值
            dividend -= value;
        }
        return result;
    }


    public static void main(String[] args) {
        Test12_整数除法 t = new Test12_整数除法();
        System.out.println(t.divide(2147483647, 2));
    }
}
